﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace TaskDuration
{
    class Program
    {
        private static Dictionary<Int32, Task> tasks = null;
        private static List<Task> taskOrder = null;
        
        internal class Task
        {
            public Int32 id;
            public Int64 duration;
            public Int64 subtreeDuration;
            public Int64 depth;
            public List<Int32> dependencies;

            public Task()
            {
                id = -1;
                duration = 0;
                depth = 0;
                subtreeDuration = -1;
                dependencies = new List<Int32>();
            }
        }

        internal enum ReadingState
        {
            NumberTasks,
            TaskDuration,
            TaskDependencies
        };

        static void Main(string[] args)
        {
            ReadingState currentState = ReadingState.NumberTasks;
            taskOrder = new List<Task>();

            StreamReader reader = new StreamReader("in");
            string buffer;

            do
            {
                buffer = reader.ReadLine();

                if (buffer.Length > 0 && buffer[0] == '#')
                {
                    continue;
                }

                switch (currentState)
                {
                    case ReadingState.NumberTasks:
                        {
                            if (string.IsNullOrEmpty(buffer))
                            {
                                currentState = ReadingState.TaskDuration;
                                break;
                            }

                            tasks = new Dictionary<int, Task>();
                        }
                        break;
                    case ReadingState.TaskDuration:
                        {
                            if (string.IsNullOrEmpty(buffer))
                            {
                                currentState = ReadingState.TaskDependencies;
                                break;
                            }

                            string[] data = buffer.Split(',');

                            Int32 taskId = Int32.Parse(data[0]);
                            Int32 taskDuration = Int32.Parse(data[1]);

                            Task t = new Task();
                            t.id = taskId;
                            t.duration = taskDuration;
                            tasks[taskId] = t;
                        }
                        break;
                    case ReadingState.TaskDependencies:
                        {
                            if (string.IsNullOrEmpty(buffer))
                            {
                                break;
                            }

                            if (buffer[0] == '#')
                            {
                                break;
                            }

                            string[] data = buffer.Split(',');
                            
                            Int32 taskId = Int32.Parse(data[0]);

                            for (Int32 i = 1; i < data.Length; i++)
                            {
                                Int32 dependencyId = Int32.Parse(data[i]);
                                tasks[taskId].dependencies.Add(dependencyId);
                                tasks[dependencyId].depth = tasks[taskId].depth + 1;

                                taskOrder.Add(tasks[dependencyId]);
                            }
                        }
                        break;
                }
            } while (!reader.EndOfStream);

            var all = from t in taskOrder orderby t.depth descending select t;

            foreach (Task t in all)
            {
                TaskMaxDuration(t.id);
            }

            TextReader consoleReader = Console.In;

            string desiredTasks = consoleReader.ReadToEnd();
            string[] selectedTasks = desiredTasks.Split(',');

            foreach (string s in selectedTasks)
            {
                Console.WriteLine(s + " " + TaskMaxDuration(Int32.Parse(s)).ToString());
            }
        }

        private static Int64 TaskMaxDuration(Int32 taskId)
        {
            Task t = tasks[taskId];

            if (t.subtreeDuration > 0)
            {
                return t.subtreeDuration;
            }

            Int64 newMax = t.duration;

            for (Int32 i = 0; i < t.dependencies.Count; i++)
            {
                Int64 tempMax = t.duration + TaskMaxDuration(t.dependencies[i]);

                if (tempMax > newMax)
                {
                    newMax = tempMax;
                }
            }

            t.subtreeDuration = newMax;

            return t.subtreeDuration;
        }
    }
}
